package tree;

import java.util.*;

public class HuffmanCode {
    public static void main(String[] args) {
      /*  String content = "乖儿子";
        //getBytes() 是Java编程语言中将一个字符串转化为一个字节数组byte[]的方法。String的getBytes()方法是得到一个系统默认的编码格式的字节数组。
        byte[] bytes = content.getBytes();
        System.out.println(bytes.length);
        List<Node> nodes = getNodes(bytes);
        System.out.println("nodes=" + nodes);
        //赫夫曼树
        Node huffmanTreeRoot = createHuffmanTree(nodes);
        System.out.println("开始遍历");
        preOrder(huffmanTreeRoot);
        //到这已经把树生成了  现在生成编码表
        getHuffmanCodes(huffmanTreeRoot, "", stringBuilder);
        System.out.println(huffmanCodes);
        byte[] zip = zip(bytes, huffmanCodes);
        System.out.println("zip="+ Arrays.toString(zip));
        System.out.println("压缩之前="+Arrays.toString(bytes));*/
        byte[] i_love_yous = huffmanZip("ash66666 dear son");
        System.out.println(Arrays.toString(i_love_yous));
        byte[] decode = decode(huffmanCodes, i_love_yous);
        System.out.println("decode=" + Arrays.toString(decode));
        String s = new String(decode);
        System.out.println(s);

    }

    /**
     * 解码
     *
     * @param bytes 要解码的数组
     * @return 返回的字符串
     */
    private static String unZip(byte[] bytes,int length) {
        //1.先将数组重新变成赫夫曼编码对应的二进制010100111

        //2.对照赫夫曼编码表重新变成字符串
        return null;
    }

    private static byte[] decode(Map<Byte, String> huffmanCodesTable, byte[] huffmanBytes) {
        //1 先得到huffmanBytes 对应的二进制字符串
        StringBuilder stringBuilder = new StringBuilder();

        Map<String, Byte> map = new HashMap<String, Byte>();
        for (Map.Entry<Byte, String> entry : huffmanCodesTable.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }
        //将byte数组转变为二进制字符串
        for (int i = 0; i < huffmanBytes.length; i++) {
            byte huffmanByte = huffmanBytes[i];
            //判断是不是最后一个字符
            boolean flag = (i == huffmanBytes.length - 1);
            int lastLength=map.get("lastLength")%8;
            stringBuilder.append(byteToBitString(huffmanByte, !flag,lastLength));
        }
        List<Byte> list = new ArrayList<>();
        for (int i = 0; i < stringBuilder.length(); ) {
            int count = 1;
            boolean flag = true;
            Byte b = null;
            while (flag) {
                String substring = stringBuilder.substring(i, i + count);
                b = map.get(substring);
                if (b == null) {
                    count++;
                } else {
                    System.out.println("b="+b+"对应的b="+Integer.toBinaryString(b));
                    flag = false;
                }
            }
            list.add(b);

                i += count;

        }
        System.out.println(huffmanCodes);
        byte[] bytes = new byte[list.size()];
        for (int i = 0; i < bytes.length; i++) {
            bytes[i] = list.get(i);
        }
        return bytes;
    }

    /**
     * 赫夫曼编码是按照补码来操作的
     *
     * @param b
     * @return
     */
    private static String byteToBitString(byte b, boolean flag,int lastLength) {

        //flag=true 时说明不是最后一位  最后一位不需要 补高位试试
        System.out.println("------------");
        //如果是正数，要补高位
        int temp = b;
        System.out.println("原来的Integer.toBinaryString(temp)={" + Integer.toBinaryString(temp) + "}");
        if (temp >= 0) {
            //1010100/////
            //flag=ture时101010100///// 是正数的时候就让不够八位的变成八位或以上
            temp |= 512;
            System.out.println("flag=true时，Integer.toBinaryString(temp)={" + Integer.toBinaryString(temp) + "}");
        }
        String s = Integer.toBinaryString(temp);

        if (flag || temp < 0) {
            //返回的是temp对应的二进制补码
            System.out.println("返回的补码"+s.substring(s.length() - 8));
            return s.substring(s.length() - 8);//最后八位
        } else {
            System.out.println("返回的补码="+s.substring(s.length() - lastLength));
            return s.substring(s.length() - lastLength);
        }

    }


    private static byte[] huffmanZip(String string) {
        if (string.equals("")) {
            return null;
        }
        byte[] bytes = string.getBytes();

        System.out.println("转换之前" + Arrays.toString(bytes));
        List<Node> nodes = getNodes(bytes);
        Node huffmanTree = createHuffmanTree(nodes);
        Map<Byte, String> huffmanCodes2 = getHuffmanCodes(huffmanTree);
        //1.利用huffmanCodes 将 bytes 转换成 赫夫曼对应的字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b : bytes) {
            //相当于先用编码表huffmanCodes找到b对应的code 再加入到builder中
            stringBuilder.append(huffmanCodes.get(b));
        }
        byte length = (byte)stringBuilder.toString().length();
        /**
         *
         */
        huffmanCodes2.put(length,"lastLength");
        return zip(bytes, huffmanCodes2);
    }

    /**
     * 编写一个方法 将 字符串对应的byte[]数组 通过 编码表 变成压缩后的编码byte[]
     *
     * @param bytes        原始
     * @param huffmanCodes 编码表
     * @return 压缩后（处理后）
     * 补码-1=反码  反码取反=原码 符号位都不用变
     */
    public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //1.利用huffmanCodes 将 bytes 转换成 赫夫曼对应的字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b : bytes) {
            //相当于先用编码表huffmanCodes找到b对应的code 再加入到builder中
            stringBuilder.append(huffmanCodes.get(b));
        }
        System.out.println("string=" + stringBuilder.toString());
        //将10110变成byte[]
        // 1.统计返回的 byte[] huffmanCodeBytes 长度
        int len;
        int index = 0;
        // len=(stringBuilder.length()+7)/8
        if (stringBuilder.length() % 8 == 0) {
            len = stringBuilder.length() / 8;
        } else {
            len = stringBuilder.length() / 8 + 1;
        }
        byte[] huffmanCodeBytes = new byte[len];
        for (int i = 0; i < stringBuilder.length(); i += 8) {
            String strByte;
            if (i + 8 > stringBuilder.length()) {

                strByte = stringBuilder.substring(i);
            } else { //(int start ,int end)
                strByte = stringBuilder.substring(i, i + 8);
            }
            //将strByte 转成一个 byte ,放入到huffmanCodeBytes
            // pareInt(String s,int redix) 将字符串s转换为redix进制的数字，默认为十进制
            //radix代表转换的进制
            //不写默认为十进制
            huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffmanCodeBytes;
    }


    /**
     * 生成赫夫曼编码表
     * {32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
     *
     * @param root
     * @return
     */
    public static Map<Byte, String> getHuffmanCodes(Node root) {
        if (root == null) {
            return null;
        }
        getHuffmanCodes(root.left, "0", stringBuilder);
        getHuffmanCodes(root.right, "1", stringBuilder);
        return huffmanCodes;
    }

    /**
     * 将编码表 放到 Map<Byte,String> 形式
     * 如 key -> value  32 ->01 97->100
     *
     * @return
     */
    static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();
    //生成赫夫曼编码表 需要拼接路径
    static StringBuilder stringBuilder = new StringBuilder();

    /**
     * 功能：将传入的Node 结点的所有叶子结点的赫夫曼编码得到 ，并放入huffmanCodes集合中
     *
     * @param node          传入结点
     * @param code          路径 左子节点 0 柚子节点 1
     * @param stringBuilder 用于拼接路径
     */
    private static void getHuffmanCodes(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        //将code 加入到 StringBuilder1
        stringBuilder1.append(code);
        if (node != null) {
            //判断node 是叶子还是非叶子
            if (node.data == null) {
                getHuffmanCodes(node.left, "0", stringBuilder1);
                getHuffmanCodes(node.right, "1", stringBuilder1);
            } else {
                huffmanCodes.put(node.data, stringBuilder1.toString());
            }
        }

    }

    private static void preOrder(Node root) {
        if (root != null) {
            root.preOder();
        } else {
            System.out.println("Node为空");
        }
    }

    private static Node createHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            Collections.sort(nodes);
            //分别取出最小和第二小的node  创建一个新的二叉树 ，它的根节点没有data 只有权值
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            Node parentNode = new Node(null, leftNode.weight + rightNode.weight);
            parentNode.left = leftNode;
            parentNode.right = rightNode;
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parentNode);
        }
        //通过循环后最后返回的节点就是根节点
        return nodes.get(0);
    }

    //将字节数组byte[]转化成arrList 首先通过哈希Map 统计出现的次数和字符 放入map中
    //再通过map的遍历方法 for (Entry<> entry:map.entrySet()) 用entry.getKey 和 getValue 方法添加到arrList中
    private static List<Node> getNodes(byte[] bytes) {
        //1创建一个arrayList
        ArrayList<Node> nodes = new ArrayList<Node>();
        //遍历bytes,统计 每一个byte出现的次数->map[key,value]
        HashMap<Byte, Integer> counts = new HashMap<>();
        for (byte b : bytes) {

            Integer count = counts.get(b);
            //merge()如果key不存在就把key-value放到map中，否则按照传入的方法更新key对应的value值。
            if (count == null) {
                counts.put(b, 1);
            } else {
                counts.put(b, count + 1);
            }
        }
        //把每一个键值对转化成一个Node 对象 ，并加入到 nodes 集合
        //遍历map
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;

    }
}

class Node implements Comparable<Node> {
    Byte data;//存放数据本身
    int weight;//权值
    Node left;
    Node right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    public void preOder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOder();
        }
        if (this.right != null) {
            this.right.preOder();
        }
    }
}